package com.zhengb.algorithmdemo.leetcode.tree;

import java.util.*;

/**
 * 二叉树中序遍历
 * https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
 *
 * @author zhengbo
 * @date 2020/3/16
 */
public class InOrderTraverseTree {

    public static void main(String[] args) {
        TreeNode one = new TreeNode(1);
        TreeNode two = new TreeNode(2);
        TreeNode three = new TreeNode(3);

        one.right = two;
        two.left = three;

        List<Integer> list = inorderTraversalWithNoRecursive(one);
        System.out.println(list);

        List<Integer> savelist = new ArrayList<>();

        inorderTraversalWithRecursive(one, savelist);

        System.out.println(savelist);
    }

    public static void inorderTraversalWithRecursive(TreeNode root, List<Integer> saveList) {

        if (root != null) {
            inorderTraversalWithRecursive(root.left, saveList);
            saveList.add(root.val);
            inorderTraversalWithRecursive(root.right, saveList);
        }
    }

    public static List<Integer> inorderTraversalWithNoRecursive(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }

        List<Integer> resultList = new LinkedList<>();

        Stack<TreeNode> stack = new Stack<>();

        TreeNode tempoNode = root;

        while (true) {
            while (tempoNode != null) {
                stack.push(tempoNode);
                tempoNode = tempoNode.left;
            }

            if (stack.isEmpty()) {
                break;
            }

            tempoNode = stack.pop();
            resultList.add(tempoNode.val);

            tempoNode = tempoNode.right;

        }
        return resultList;
    }
}
